import javafx.scene.layout.Priority;

import java.util.*;

/**
 * Created by L.jp
 * Description:给一非空的单词列表，返回前 k 个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
 * User: 86189
 * Date: 2021-10-28
 * Time: 19:49
 */
public class HighFrequencyWords {
    public static  List<String> topKFrequent(String[] words, int k) {
        //统计单词出现的次数
        HashMap<String,Integer> map=new HashMap<>();
        for(String str:words){
            if(map.get(str)==null){//不是0，因为value是引用类型
                map.put(str,1);
            }else{
                int val=map.get(str);
                map.put(str,val+1);
            }
        }
        //构造小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){//建堆时要考虑到两个值value相等时，就调用compareTo方法返回其key值大小
                    return o2.getKey().compareTo(o1.getKey());//如果value值相同，因为最终还是要根据字母顺序从小到大输出，又因为最后总要逆置，当value值相同时，小的字母总是在前面输出，所以此时要建为大堆，最后逆置输出才是按字母顺序输出，符合题目要求
                }
                return o1.getValue()-o2.getValue();//当key值不一样是，直接用value值相减
            }
        });
        //把map包装成entrySet放到小根堆中
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k) {
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0) {//当堆顶的值和entry的值相等
                    if (top.getKey().compareTo(entry.getKey()) > 0) {//但是单词不一样时,如果堆顶字母比entry的大，那么就要弹出堆顶的，将字母更小的那个入堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    if(top.getValue().compareTo(entry.getValue())<0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        //把小根堆的前k个单词放入List中，因为返回值类型是List
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++){
            Map.Entry<String,Integer> top1=minHeap.poll();
            if(top1!=null){
                list.add(top1.getKey());//只把前k个单词放入
            }
        }
        //此时list存放的是按照小根堆的从低到高的顺序
        Collections.reverse(list);//逆置，从高到低
        return list;
    }

    public static void main(String[] args) {
        String[]words={"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> ret=topKFrequent(words,4);
        System.out.println(ret);
    }
}

